We first show that the Traveling Salesman Problem in an n-vertex graph withaverage degree bounded by d can be solved in O*(2^{(1-\eps_d)n}) time andexponential space for a constant \eps_d depending only on d, where theO*-notation suppresses factors polynomial in the input size. Thus, wegeneralize the recent results of Bjorklund et al. [TALG 2012] on graphs ofbounded degree. Then, we move to the problem of counting perfect matchings in a graph. Wefirst present a simple algorithm for counting perfect matchings in an n-vertexgraph in O*(2^{n/2}) time and polynomial space; our algorithm matches thecomplexity bounds of the algorithm of Bjorklund [SODA 2012], but relies oninclusion-exclusion principle instead of algebraic transformations. Buildingupon this result, we show that the number of perfect matchings in an n-vertexgraph with average degree bounded by d can be computed inO*(2^{(1-\eps_{2d})n/2}) time and exponential space, where \eps_{2d} is theconstant obtained by us for the Traveling Salesman Problem in graphs of averagedegree at most 2d. Moreover we obtain a simple algorithm that counts the number of perfectmatchings in an n-vertex bipartite graph of average degree at most d inO*(2^{(1-1/(3.55d))n/2}) time, improving and simplifying the recent result ofIzumi and Wadayama [FOCS 2012].
展开▼
